#include <stdio.h>
#include <stdlib.h>
#include <string.h>

/**
 * 삽입정렬 : 제자리를 찾을때까지 한칸씩 밀어서 자리를 마련
 * 오름차순(작은수 - 큰수)
 */


// 비교 함수 : a가 크면 1, b가 크면 -1, 같으면 0

#define STACK_MAX   500    
int cmp(int a, int b) {
    if (a == b) {
        return 0;
    }
    else if (a > b) {
        return 1;
    }
    else {
        return -1;
    }
}

inline void swap(int* a, int* b) {
    int tmp = *a;
    *a = *b;
    *b = tmp;
}

struct STACK_ITEM{
    // fill arguments
    int left;
    int right;
};

struct STACK{
    struct STACK_ITEM array[STACK_MAX];
    int pos;
};

int stack_init(struct STACK* stack) {
    stack->pos = 0;
}

int stack_push(struct STACK* stack, struct STACK_ITEM* item) {
    if (stack->pos == STACK_MAX) {
        printf("[%s] stack full!\n", __FUNCTION__);
        return -1;
    }
    memcpy(&(stack->array[stack->pos]), item, sizeof(struct STACK_ITEM));        
    stack->pos = stack->pos + 1;
    printf("stack push p=%d l=%d r=%d\n", stack->pos, item->left, item->right);
    return stack->pos;
}

int stack_pop(struct STACK* stack, struct STACK_ITEM* item) {
    if (stack->pos == 0) {
        printf("[%s] stack empty!\n", __FUNCTION__);
        return -1;
    }
    stack->pos = (stack->pos - 1);
    memcpy(item, &(stack->array[stack->pos]), sizeof(struct STACK_ITEM));
    return stack->pos;
}

int stack_is_empty(struct STACK* stack) {
    return (stack->pos == 0);
}

//////////////////////////////////////////////////////////////////////////////////

// 정해진 구간에서 pivotIndex가 가리키는 값의 정확한 위치를 찾아 위치시켜 준다.
int partition(int* array, int(*pcmp)(int, int), int left, int right, int pivotIndex) {
    int idx,store;
    int pivot = array[pivotIndex];

    // 기준값을 배열의 끝으로 이동
    swap(&array[right], &array[pivotIndex]);

    // 기준보다 작은 모든 값을 배열의 앞쪽으로 이동하고 기준값을 이들 값
    // 바로 뒤로 옮긴다.
    store = left;
    for (idx = left; idx < right; idx++) {
        if (pcmp(array[idx], pivot) <= 0) {
            swap(&array[idx], &array[store]);
            store++;
        }
    }

    swap(&array[right] /*pivot value*/, &array[store]);
    return store;
}

int median_sort(int* array, int count, int order, int(*pcmp)(int,int)) {
    int i;
    int done = 0;
    int left,right,mid, median, pivotIndex;
    struct STACK stack;
    struct STACK_ITEM stack_item;
    stack_init(&stack);
   
    left = 0;
    right = count-1;

    stack_item.left = 0;
    stack_item.right = count-1;
    stack_push(&stack, &stack_item);

    while(!stack_is_empty(&stack)) {

        stack_pop(&stack, &stack_item);
        left = stack_item.left;
        right = stack_item.right;
        printf("popped: left=%d right=%d\n", left, right);
        
        if (left < right) {
            pivotIndex = (left + right)/2;

            mid = partition(array, pcmp, left, right, pivotIndex);

            stack_item.left = left;
            stack_item.right = mid - 1;
            stack_push(&stack, &stack_item);
            printf("push: left=%d right=%d\n", stack_item.left, stack_item.right);
            
            stack_item.left = mid + 1;
            stack_item.right = right;
            stack_push(&stack, &stack_item);
            printf("push: left=%d right=%d\n", stack_item.left, stack_item.right);
        }
    }
}

//////////////////////////////////////////////////////////////////////////////////

#define DATA_COUNT 11
int main(int argc,char** argv) {
    int i;
    int a[DATA_COUNT] = { 1, 8, 9, 7, 4, 3, 6, 5, 2, 10, 10};    
    median_sort(a, DATA_COUNT, 0, cmp);
    
    for (i = 0; i < DATA_COUNT; i++) {
        printf("%d ", a[i]);
    }
    printf("\n");
    return 0;
}

